package com.LeeCode;

/**
 * 零数组变换Ⅱ
 */

public class Code3356 {
    public static void main(String[] args) {

    }

    public int minZeroArray(int[] nums, int[][] queries) {
        int left = -1, right = queries.length + 1;

        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (check(mid, nums, queries)) {
                right = mid;
            } else {
                left = mid;
            }
        }
        return right <= queries.length ? right : -1;
    }

    public boolean check(int k, int[] nums, int[][] queries) {
        int[] count = new int[nums.length + 1];
        for (int i = 0; i < k; i++) {
            count[queries[i][0]] += queries[i][2];
            count[queries[i][1] + 1] -= queries[i][2];
        }

        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += count[i];
            if (nums[i] != 0 && sum < nums[i]) {
                return false;
            }
        }
        return true;
    }

    // 双指针解法
    public int minZeroArray1(int[] nums, int[][] queries) {
        int n = nums.length;
        int[] diff = new int[n + 1];
        int sumD = 0;
        int k = 0;
        for (int i = 0; i < n; i++) {
            int x = nums[i];
            sumD += diff[i];
            while (k < queries.length && sumD < x) { // 需要添加询问，把 x 减小
                int[] q = queries[k];
                int l = q[0], r = q[1], val = q[2];
                diff[l] += val;
                diff[r + 1] -= val;
                if (l <= i && i <= r) { // x 在更新范围中
                    sumD += val;
                }
                k++;
            }
            if (sumD < x) { // 无法更新
                return -1;
            }
        }
        return k;
    }
}
